/*
 * Project: BoboDesignPattern
 * 
 * File Created at 2019年6月8日
 * 
 * Copyright 2012 Greenline.com Corporation Limited.
 * All rights reserved.
 *
 * This software is the confidential and proprietary information of
 * Greenline Company. ("Confidential Information").  You shall not
 * disclose such Confidential Information and shall use it only in
 * accordance with the terms of the license agreement you entered into
 * with Greenline.com.
 */
package test.lesson3.tree.binarytree.sorttree;

/**
 * @Type BinarySortTree
 * @Desc
 * @author 52489
 * @date 2019年6月8日
 * @Version V1.0
 */
public class BinarySortTree {
    Node root;

    public void add(Node node) {
        if (null == root) {
            root = node;
        } else {
            root.add(node);
        }
    }

    public void midleShow() {
        if (null != root) {
            root.midleShow(root);
        }
    }

    public Node search(int value) {
        if (null == root) {
            return null;
        } else {
            return root.search(value);
        }
    }

    public void delete(int value) {
        if (null == root) {
            return;
        } else {
            Node target = search(value);

            if (target == null) {
                return;
            }

            Node parent = searchParent(value);
            // 要删除的节点是叶子节点
            if (target.left == null && target.right == null) {
                if (parent.left.value == value) {
                    parent.left = null;

                } else {
                    parent.right = null;
                }
                // 要删除的节点有两个子节点的情况
            } else if (target.left != null & target.right != null) {
                // 删除右子树中值最小的节点，获取到该节点的值
                int min = deleteMin(target.right);
                // 替换目标节点的值
                target.value = min;

                // 要删除的节点有一个左子节点或右子节点
            } else {
                // 有左子节点
                if (target.left != null) {
                    // 要删除的节点是父节点的左子节点、
                    if (parent.left.value == value) {
                        parent.left = target.right;
                        // 要删除的节点是父节点的右子节点
                    } else {
                        parent.right = target.left;
                    }
                    // 有右子节点
                } else {
                    // 要删除的节点是父节点的左子节点
                    if (parent.left.value == value) {
                        parent.left = target.right;
                        // 要删除的节点是父节点的右子节点
                    } else {
                        parent.right = target.right;
                    }
                }
            }
        }

    }

    /**
     * 删除一棵树中最小的节点
     * 
     * @param right
     * @return
     */
    private int deleteMin(Node node) {
        Node target = node;
        // 递归向左找
        while (target.left != null) {
            target = target.left;
        }
        // 删除最小的节点
        delete(target.value);
        return target.value;
    }

    /**
     * 搜搜父节点
     * 
     * @return
     */
    public Node searchParent(int value) {
        if (null == root) {
            return null;

        } else {
            return root.searchParent(value);
        }

    }
}
